package ljl.alg.wangzheng_camp.round1.bfsdfs;

import java.util.LinkedList;

/**
* dfs bfs 和并查集
* 莫非你还能想出来什么颠覆性的解法？no！
* */
public class _200_islands {
    
    /**
     * 历史重演
     * 我以为的 bfs 其实是 dfs
     * */
    static class dfs {
        public int numIslands(char[][] grid) {
            int m = grid.length, n = grid[0].length;
            int count = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1') {
                        count++;
                        dfs(grid, i, j);
                    }
                }
            }
            return count;
        }
        
        void dfs(char[][] grid, int i, int j) {
            if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0')
                return;
            grid[i][j] = '0';
            dfs(grid, i + 1, j);
            dfs(grid, i - 1, j);
            dfs(grid, i, j - 1);
            dfs(grid, i, j + 1);
        }
    }
    
    static class bfs {
        public int numIslands(char[][] grid) {
            int m = grid.length, n = grid[0].length;
            int count = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1') {
                        grid[i][j] = 0;
                        count++;
                        LinkedList<Integer> q = new LinkedList<>();
                        q.offer(n * i + j);
                        while (!q.isEmpty()) {
                            int offset = q.poll();
                            int row = offset / n;
                            int col = offset % n;
                            if (row - 1 >= 0 && grid[row - 1][col] == '1') {
                                grid[row - 1][col] = '0';
                                q.offer((row - 1) * n + col);
                            }
                            if (row + 1 < m && grid[row + 1][col] == '1') {
                                grid[row + 1][col] = '0';
                                q.offer((row + 1) * n + col);
                            }
                            if (col + 1 < n && grid[row][col + 1] == '1') {
                                grid[row][col + 1] = '0';
                                q.offer(row * n + col + 1);
                            }
                            if (col - 1 >= 0 && grid[row][col - 1] == '1') {
                                grid[row][col - 1] = '0';
                                q.offer(row * n + col - 1);
                            }
                        }
                    }
                }
            }
            return count;
        }
    }
    
    /**
     * 复习一遍并查集！呀！
     * */
    static class union_find {
        static class UnionFind {
            int[] parent, rank;
            int count;
            UnionFind(char[][] grid) {
                int m = grid.length, n = grid[0].length;
                parent = new int[m * n];
                rank = parent.clone();
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        if (grid[i][j] == '1') {
                            count++;
                            parent[i * n + j] = i * n + j;
                        }
                    }
                }
            }
        
            int find(int x) {
                if (parent[x] != x) parent[x] = find(parent[x]);
                return parent[x];
            }
        
            /**
             * 判断两个 root 的 rank，然后修改两个 root 的父子关系，不干其它人的事！
             * */
            void union(int x, int y) {
                int rootX = find(x), rootY = find(y);
                if (rootX != rootY) {
                    count--;
                    if (rank[rootX] > rank[rootY]) {
                        parent[rootY] = rootX;
                    } else if (rank[rootX] < rank[rootY]) {
                        parent[rootX] = rootY;
                    } else {
                        parent[rootY] = rootX;
                        rank[rootX]++;
                    }
                }
            }
        }
        public int numIslands(char[][] grid) {
            int m = grid.length, n = grid[0].length;
            UnionFind uf = new UnionFind(grid);
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1') {
                        grid[i][j] = '0';
                        if (i - 1 >= 0 && grid[i - 1][j] == '1') uf.union(offset(i - 1, j, n), offset(i, j, n));
                        if (i + 1 < m && grid[i + 1][j] == '1') uf.union(offset(i + 1, j, n), offset(i, j, n));
                        if (j - 1 >= 0 && grid[i][j - 1] == '1') uf.union(offset(i, j - 1, n), offset(i, j, n));
                        if (j + 1 < n && grid[i][j + 1] == '1') uf.union(offset(i, j + 1, n), offset(i, j, n));
                    }
                }
            }
            return uf.count;
        }
        int offset(int i, int j, int n) {
            return i * n + j;
        }
    }
    
}
